package com.whitedust.top10;

/**
 * @author A
 * @since 2025/11/2 13:46
 */

public class Top10 {
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for(int i = s.length()-1;i>0;i--){
            for(int j= i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)&&(j-i<=2||dp[i+1][j-1])){
                    dp[i][j] = true;
                    if (j - i + 1 > res.length()) {
                        res = s.substring(i, j + 1);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Top10 top10 = new Top10();
        System.out.println(top10.longestPalindrome("babad"));
    }
}

